package 每日一题;

import java.util.Map;
import java.util.TreeMap;

/**
 * 剑指 Offer II 058. 日程表
 * 请实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内没有其他安排，则可以存储这个新的日程安排。
 *
 * MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排，注意，这里的时间是半开区间，即 [start, end), 实数 x 的范围为，  start <= x < end。
 *
 * 当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生重复预订。
 *
 * 每次调用 MyCalendar.book方法时，如果可以将日程安排成功添加到日历中而不会导致重复预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。
 *
 * 请按照以下步骤调用 MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)
 *
 *
 *
 * 示例:
 *
 * 输入:
 * ["MyCalendar","book","book","book"]
 * [[],[10,20],[15,25],[20,30]]
 * 输出: [null,true,false,true]
 * 解释:
 * MyCalendar myCalendar = new MyCalendar();
 * MyCalendar.book(10, 20); // returns true
 * MyCalendar.book(15, 25); // returns false ，第二个日程安排不能添加到日历中，因为时间 15 已经被第一个日程安排预定了
 * MyCalendar.book(20, 30); // returns true ，第三个日程安排可以添加到日历中，因为第一个日程安排并不包含时间 20
 *
 *
 *
 *
 * 提示：
 *
 * 每个测试用例，调用 MyCalendar.book 函数最多不超过 1000次。
 * 0 <= start < end <= 109
 *
 *
 * 注意：本题与主站 729 题相同： https://leetcode-cn.com/problems/my-calendar-i/
 */
public class D220721_TOfferII_058 {
    class MyCalendar {

        // 差分数组
        TreeMap<Integer, Integer> diff;

        public MyCalendar() {
            diff = new TreeMap<>();
        }

        public boolean book(int start, int end) {

            //假设可以插入 先将日程插入

            diff.put(start, diff.getOrDefault(start, 0) + 1);

            diff.put(end, diff.getOrDefault(end, 0) - 1);


            int count = 0;
            for (Map.Entry<Integer, Integer> entry : diff.entrySet()) {
                count += entry.getValue();
                //count 大于1 说明在这个时间里出现 重复日程
                if (count > 1) {
                    //删除刚插入的日程
                    diff.put(start, diff.get(start) - 1);
                    diff.put(end, diff.get(end) + 1);

                    if (diff.get(start) == 0) {
                        diff.remove(start);
                    }
                    if (diff.get(end) == 0) {
                        diff.remove(end);
                    }
                    return false;
                }
            }
            if (diff.get(start) == 0) {
                diff.remove(start);

            }
            if (diff.get(end) == 0) {
                diff.remove(end);
            }

            return true;

        }


    }

    public static void main(String[] args) {
        MyCalendar myCalendar = new D220721_TOfferII_058().new MyCalendar();
        myCalendar.book(10, 20);
        myCalendar.book(15, 25);
        myCalendar.book(20, 30);

    }
}
